<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>采用DFA算法实现 - lexer词法分析器；生成tokens</title>
</head>
<body>
  <script type="module">
    import { getFile } from './getFile.js';
    /** -----纯函数-----begin **/
    // 数值类型扫描器
    function scanNumber(code, i) {
      const len = code.length;
      let scanPos = i;    // 当前扫描指针，从起始位置 i 开始
      let sawDot = false; // 标记是否已经遇到小数点（用于后续判断 BigInt 后缀合法性）
      let sawExp = false; // 标记是否已经遇到指数符号 e/E（同样用于 BigInt 合法性判断）

      const scan = (re) => {
        while (scanPos < len && re.test(code[scanPos])) scanPos++;
      };

      // 以 '.' 开头的小数，如 .5
      if (code[scanPos] === '.') {
        sawDot = true;
        scanPos++;
        scan(/\d/);
      } else {
        // 处理 0x / 0o / 0b 前缀数或十进制
        if (code[scanPos] === '0' && scanPos + 1 < len) {
          const p = code[scanPos + 1];
          // 16 进制
          if (p === 'x' || p === 'X') {
            scanPos += 2; // 跳过 0x
            const start = scanPos;
            scan(/[0-9a-fA-F]/);
            // 至少要有一位 16 进制数字
            if (scanPos === start) return { lexeme: '0', end: i + 1 };
            // BigInt 后缀 n（可选）
            if (scanPos < len && code[scanPos] === 'n') scanPos++;
            return { lexeme: code.slice(i, scanPos), end: scanPos };
          }
          // 2 进制
          if (p === 'b' || p === 'B') {
            scanPos += 2; // 跳过 0b
            const start = scanPos;
            scan(/[01]/);
            if (scanPos === start) return { lexeme: '0', end: i + 1 };
            if (scanPos < len && code[scanPos] === 'n') scanPos++;
            return { lexeme: code.slice(i, scanPos), end: scanPos };
          }
          // 8 进制
          if (p === 'o' || p === 'O') {
            scanPos += 2; // 跳过 0o
            const start = scanPos;
            scan(/[0-7]/);
            if (scanPos === start) return { lexeme: '0', end: i + 1 };
            if (scanPos < len && code[scanPos] === 'n') scanPos++;
            return { lexeme: code.slice(i, scanPos), end: scanPos };
          }
        }

        // 继续扫描是不是十进制数值
        scan(/\d/);

        // 小数点部分（可选），支持 1. 或 1.23
        if (scanPos < len && code[scanPos] === '.') {
          sawDot = true;
          scanPos++;
          scan(/\d/);
        }
      }

      // 指数部分 e/E(+/-)?digits（可选）
      if (scanPos < len && (code[scanPos] === 'e' || code[scanPos] === 'E')) {
        const expStart = scanPos;
        scanPos++;
        if (scanPos < len && (code[scanPos] === '+' || code[scanPos] === '-')) scanPos++;
        const expDigitsStart = scanPos;
        scan(/\d/);
        // 若 e 之后没有数字，则回退，不算指数
        if (scanPos === expDigitsStart) {
          scanPos = expStart;
        } else {
          sawExp = true;
        }
      }

      // BigInt 后缀 n：仅当无小数点且无指数时允许
      if (!sawDot && !sawExp && scanPos < len && code[scanPos] === 'n') {
        scanPos++;
      }

      return { lexeme: code.slice(i, scanPos), end: scanPos };
    }
    // 标识符类型扫描器
    function scanIdentifier(code, i) {
      const len = code.length;
      let scanPos = i;
      // 匹配标识符开头
      if (!idBegin.test(code[scanPos])) return null;
      scanPos++;
      // 匹配后续标识符
      while (scanPos < len && idContinue.test(code[scanPos])) scanPos++;
      return { lexeme: code.slice(i, scanPos), end: scanPos };
    }
    // 字符串类型扫描器
    function scanString(code, i) {
      const len = code.length;
      const quote = code[i];
      let pos = i + 1;
      let out = "";

      const isHex = (ch) => /[0-9a-fA-F]/.test(ch);
      debugger;
      while (pos < len) {
        const ch = code[pos];
        debugger;
        // 处理转义
        if (ch === '\\') {
          pos++;
          if (pos >= len) break;
          const esc = code[pos];
          switch (esc) {
            case 'n': out += '\n'; break; // 换行符  例: "line1\nline2" → 实际两行
            case 'r': out += '\r'; break; // 回车符  例: "abc\r123" → 光标回行首再输出123
            case 't': out += '\t'; break; // 水平制表符  例: "a\tb" → a与b间一个Tab空白
            case 'b': out += '\b'; break; // 退格符  例: "ab\b" → 实际得到a
            case 'f': out += '\f'; break; // 换页符  例: "page1\fpage2" → 打印时换到新一页
            case 'v': out += '\v'; break; // 垂直制表符  例: "a\vb" → 纵向跳格，效果类似竖向Tab
            case '0': out += '\0'; break; // NUL字符  例: "a\0b" → 中间插入0x00空字节
            case '\\': out += '\\'; break; // 反斜杠  例: "C:\\path" → 实际得到C:\path
            case '"': out += '"'; break;   // 双引号  例: "say \"hi\"" → 字符串含双引号
            case "'": out += "'"; break;   // 单引号  例: 'it\'s' → 字符串含单引号
            case 'x': {
              const h1 = code[pos + 1];
              const h2 = code[pos + 2];
              if (isHex(h1) && isHex(h2)) {
                out += String.fromCharCode(parseInt(h1 + h2, 16));
                pos += 2;
              } else {
                // 非法 \x 转义，按原字符处理
                out += 'x';
              }
              break;
            }
            case 'u': {
              // 支持 \uXXXX 与 \u{...}
              const hex4 = code.slice(pos + 1, pos + 5);
              if (/^[0-9a-fA-F]{4}$/.test(hex4)) {
                out += String.fromCharCode(parseInt(hex4, 16));
                pos += 4;
              } else if (code[pos + 1] === '{') {
                let k = pos + 2, hex = '';
                while (k < len && code[k] !== '}') hex += code[k++];
                if (code[k] === '}' && /^[0-9a-fA-F]+$/.test(hex)) {
                  out += String.fromCodePoint(parseInt(hex, 16));
                  pos = k;
                } else {
                  out += 'u';
                }
              } else {
                out += 'u';
              }
              break;
            }
            default:
              out += esc;
          }
          pos++;
          continue;
        }

        // 正常字符或遇到结束引号
        if (ch === quote) {
          const end = pos + 1;
          // 返回原始切片以与数字/符号保持一致风格
          return { lexeme: code.slice(i, end), end };
        }

        // 非法换行（未闭合字符串）
        if (ch === '\n' || ch === '\r') {
          break;
        }

        out += ch;
        pos++;
      }

      // 未闭合字符串：消耗至当前位置，返回原始切片
      return { lexeme: code.slice(i, pos), end: pos };
    }
    // template类型扫描器
    function scanTemplate(code, i) {
      const len = code.length;
      let pos = i;
      let out = "";
      // 模板必须以 ` 开头
      if (code[pos] !== '`') return null;
      pos++; // 跳过起始 `
      while (pos < len) {
        const ch = code[pos];
        // 遇到反引号，结束
        if (ch === '`') {
          pos++;
          return { lexeme: code.slice(i, pos), end: pos };
        }
        // 遇到 ${ 开始表达式插值
        if (ch === '\\' && pos + 1 < len) {
          // 处理模板字符串中的转义
          const next = code[pos + 1];
          switch (next) {
            case '`': out += '`'; pos += 2; continue;
            case '\\': out += '\\'; pos += 2; continue;
            case '$': out += '$'; pos += 2; continue;
            case 'n': out += '\n'; pos += 2; continue;
            case 'r': out += '\r'; pos += 2; continue;
            case 't': out += '\t'; pos += 2; continue;
            case 'b': out += '\b'; pos += 2; continue;
            case 'f': out += '\f'; pos += 2; continue;
            case 'v': out += '\v'; pos += 2; continue;
            case '0': out += '\0'; pos += 2; continue;
            case 'x': {
              const h1 = code[pos + 2];
              const h2 = code[pos + 3];
              if (/^[0-9a-fA-F]$/.test(h1) && /^[0-9a-fA-F]$/.test(h2)) {
                out += String.fromCharCode(parseInt(h1 + h2, 16));
                pos += 4;
              } else {
                out += 'x';
                pos += 2;
              }
              continue;
            }
            case 'u': {
              if (code[pos + 2] === '{') {
                let k = pos + 3, hex = '';
                while (k < len && code[k] !== '}') hex += code[k++];
                if (code[k] === '}' && /^[0-9a-fA-F]+$/.test(hex)) {
                  out += String.fromCodePoint(parseInt(hex, 16));
                  pos = k + 1;
                } else {
                  out += 'u';
                  pos += 2;
                }
              } else {
                const hex4 = code.slice(pos + 2, pos + 6);
                if (/^[0-9a-fA-F]{4}$/.test(hex4)) {
                  out += String.fromCharCode(parseInt(hex4, 16));
                  pos += 6;
                } else {
                  out += 'u';
                  pos += 2;
                }
              }
              continue;
            }
            default:
              out += next;
              pos += 2;
              continue;
          }
        }
        if (ch === '$' && pos + 1 < len && code[pos + 1] === '{') {
          // 进入插值表达式，需递归词法分析或跳过至匹配 '}'
          let depth = 1;
          pos += 2; // 跳过 ${
          while (pos < len && depth > 0) {
            const c = code[pos];
            if (c === '{') depth++;
            else if (c === '}') depth--;
            pos++;
          }
          // 如果depth为0，说明匹配到结束}，继续扫描模板剩余部分
          if (depth === 0) {
            continue;
          } else {
            // 未闭合插值，直接返回当前切片
            return { lexeme: code.slice(i, pos), end: pos };
          }
        }
        // 普通字符
        out += ch;
        pos++;
      }
      // 未闭合模板字符串
      return { lexeme: code.slice(i, pos), end: pos };
    }


    /**
     * 构建字典树
     * **/
    function buildTrie(list) {
      const root = {};
      for (const op of list) {
        let node = root;
        for (const ch of op) node = (node[ch] ||= {});
        node.$ = true; // 终止标记
      }
      return root;
    }
    /** -----纯函数-----end **/

    // 词法分析器
    function createLexer() {
      // 匹配关键字
      const keywords = /^(?:break|case|catch|continue|debugger|default|do|else|finally|for|function|if|return|switch|throw|try|var|let|const|while|with|null|true|false|instanceof|typeof|void|delete|new|in|this|class|extends|export|import|super)$/;
      // 匹配标识符开头（不允许数字）
      const idBegin = /^[a-zA-Z_$]$/;
      // 匹配后续标识符（允许数字）
      const idContinue = /^[a-zA-Z0-9_$]$/;
      // 匹配符号
      const op = /[{}\(\)\[\];,:\.?~!+\-*\/%&|^<>=]/;

      // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Unsigned_right_shift_assignment
      const punctList = [
        '>>>=','===','!==','<<=','>>=','**=','&&=','||=','??=','>>>','...',
        // 双运算符
        '==','!=','<=','>=','&&','||','++','--','+=','-=','*=','/=','%=',
        '&=','|=','^=','<<','>>','**','??','=>',
        // 单
        '{','}','(',')','[',']',';',',',':','.','?','~','!','+','-','*','/','%','&','|','^','<','>','='
      ];

      const trie = buildTrie(punctList);

      function nextPunctuator(code, i) {
        let node = trie, j = i, lastEnd = -1;
        while (j < code.length && node[code[j]]) {
          node = node[code[j++]];
          if (node.$) lastEnd = j;     // 记录最近的可接受终点（最长优先）
        }
        return lastEnd >= 0 ? { lexeme: code.slice(i, lastEnd), end: lastEnd } : null;
      }



      const TokenTypes = Object.freeze({
        ID: 'Identifier',
        KW: 'Keyword',
        NUM: 'Numeric',
        STR: 'String',
        TPL: 'Template',
        OP: 'Punctuator',
        SPACE: 'Whitespace',
        RE: 'RegularExpression',
        BOOL: 'Boolean',
        NULL: 'Null',
        EOF: '<end>'
      });

      // 词法分析器内部状态对象
      const lexerStateFn = () => {
        return {
          code: "",
          tokens: [],
          state: "Start",
          buffer: "",
          i: 0
        };
      };

      const lexerState = lexerStateFn();

      const resetLexerState = (options) => {
        Object.assign(lexerState, lexerStateFn(), options);
      }

      // 重置state
      const resetBufferAndState = () => {
        lexerState.state = "Start";
        lexerState.buffer = "";
      };

      // 前瞻 n 个字符
      function peek(n = 0) {
        const { code, i } = lexerState;
        return code[i + n] || "";
      }

      // function isSpace(ch) {
      //   const { i, code } = lexerState;
      //   return /\s/.test(ch) && i < code.length;
      // }

      // 采用DFA算法（确定有限状态自动机）
      const stateMap = {
        "Start": (ch) => {
          const { i, code } = lexerState;
          // 匹配空白字符（立即派发）
          if (/\s/.test(ch)) {
            lexerState.state = TokenTypes.SPACE;
            stateMap[lexerState.state](ch);
            return;
          }
          // 匹配标识符（立即派发：Start 不收集、不前进 i）
          if (idBegin.test(ch)) {
            lexerState.state = TokenTypes.ID;
            stateMap[lexerState.state](ch);
            return;
          }
          
          // 匹配数字（立即派发：Start 不收集、不前进 i）
          if (/^\d/.test(ch) || (ch === '.' && /\d/.test(peek(1)))) {
            lexerState.state = TokenTypes.NUM;
            stateMap[lexerState.state](ch);
            return;
          }
          // 匹配符合（立即派发）
          if (op.test(ch)) {
            lexerState.state = TokenTypes.OP;
            stateMap[lexerState.state](ch);
            return;
          }
          // 匹配字符串字面量（立即派发）
          if (ch === '"' || ch === "'") {
            lexerState.state = TokenTypes.STR;
            stateMap[lexerState.state](ch);
            return;
          }
        },
        // 匹配空白符
        [TokenTypes.SPACE]: (ch) => {
          const { buffer, i, code, tokens } = lexerState;
          if (/\s/.test(ch)) {
            Object.assign(lexerState, {
              buffer: ch,
              tokens: [...tokens, { type: TokenTypes.SPACE, value: ch }],
              i: i + 1
            });
            return;
          }
          resetBufferAndState();
        },
        // 匹配标识符
        [TokenTypes.ID]: (ch) => {
          const { buffer, i, code, tokens } = lexerState;
          // 如果下一个字符仍是标识符的“继续字符”，继续收集并前进
          if (idContinue.test(ch)) {
            Object.assign(lexerState, {
              buffer: buffer + ch,
              i: i + 1
            });
            return;
          }
          // 否则遇到边界，按关键字/标识符规则 flush
          if (keywords.test(buffer)) {
            Object.assign(lexerState, {
              tokens: [...tokens, { type: TokenTypes.KW, value: buffer }]
            });
          } else {
            Object.assign(lexerState, {
              tokens: [...tokens, { type: TokenTypes.ID, value: buffer }]
            });
          }
          resetBufferAndState();
        },
        // 匹配符合
        [TokenTypes.OP]: (ch) => {
          const { buffer, i, code, tokens } = lexerState;
          const hit = nextPunctuator(code, i);
          const { lexeme, end } = hit;
          if (hit) { 
            Object.assign(lexerState, {
              buffer: lexeme,
              i: end,
              tokens: [...tokens, { type: TokenTypes.OP, value: lexeme }],
            });
          }else {
            throw new Error(`Unexpected punctuator ${ch}`);
          }
          resetBufferAndState();
        },
        // 匹配数字
        [TokenTypes.NUM]: (ch) => { 
          // 从数字起始位置一次性读取完整字面量
          const { buffer, i, code, tokens } = lexerState;
          const { end, lexeme } = scanNumber(code, i);
          if (end > i) {
            Object.assign(lexerState, {
              buffer: lexeme,
              i: end,
              tokens: [...tokens, { type: TokenTypes.NUM, value: lexeme }],
            });
          }
          resetBufferAndState();
        },
        // 匹配字符串
        [TokenTypes.STR]: (ch) => {
          const { buffer, i, code, tokens } = lexerState;
          const { end, lexeme } = scanString(code, i);
          if (end > i) {
            Object.assign(lexerState, {
              buffer: lexeme,
              i: end,
              tokens: [...tokens, { type: TokenTypes.STR, value: lexeme }],
            });
          }
          resetBufferAndState();
        },
        // 匹配模板字符串
        [TokenTypes.TPL]: (ch) => { 
          const { buffer, i, code, tokens } = lexerState;
          debugger;
          const { end, lexeme } = scanTemplate(code, i);
          if (end > i) {
            Object.assign(lexerState, {
              buffer: lexeme,
              i: end,
              tokens: [...tokens, { type: TokenTypes.TPL, value: lexeme }],
            });
          }
          resetBufferAndState();
        },
        // EOF模式
        [TokenTypes.EOF]: (lastState) => {
          if(!lexerState.buffer) return;
          lexerState.tokens = [
              ...lexerState.tokens, 
            { type: lastState, value: lexerState.buffer }
          ];
        }
      }

      // 返回tokenize函数
      return {
        tokenize(code) { 
          /**
           * 重置词法分析的内部数据
           * **/
          resetLexerState({ code });
          // 开始词法分析
          while (lexerState.i < code.length) {
            const { state, i } = lexerState;
            stateMap[state](code[i]);
          }
          stateMap[TokenTypes.EOF](lexerState.state);
          return lexerState.tokens;
        },
        parse() {

        }
      }
    }

    const { tokenize } = createLexer();

    // console.log(
    //   tokenize(`
    //     let a
    //   `)
    // );

    // console.log(tokenize(`23.45`));

    // console.log(tokenize(`const a = 1.23;`));

    // console.log(tokenize(`const a = 2e-3;`));

    // console.log(tokenize(`const a = 0b011;`));

    // console.log(tokenize(`const a = 0o123;`));

    // console.log(tokenize(`const a = 0x123;`));

    // console.log(tokenize(`const a = 123n;`));

    getFile('./str.js').then((content) => {
      console.log(tokenize(content));
    })

    console.log(tokenize("const name = `ck`; "))

    
  </script>
</body>



</html>